import java.util.HashMap;
import java.util.Map;


class LRUCache<K,V> {

    class ValueNode<K,V>{
        private K key;
        private V value;
        private ValueNode<K,V> last;
        private ValueNode<K,V> next;

        public ValueNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private Map<K,ValueNode<K,V>> cache;
    private ValueNode<K,V> head;
    private ValueNode<K,V> tail;
    private int cacheSize;

    public LRUCache(int cacheSize){
        cache = new HashMap<>(cacheSize);
        this.cacheSize = cacheSize;
    }

    private boolean removeNodeIfNotTail(ValueNode node){ //返回是否删除
        ValueNode<K,V> next = node.next;
        ValueNode<K,V> last = node.last;
        if(next != null){
            next.last = last;
        }
        else{
            return false; //原本就在队尾
        }
        if(last != null){
            last.next = next;
        }
        else{
            head = next;
        }
        return true;
    }

    private void pushBack(ValueNode<K,V> node){
        if(tail == null){
            head = tail = node;
            return;
        }
        tail.next = node;
        node.last = tail;
        node.next = null;
        tail = node;
    }

    private void removeHead(){
        head = head.next;
        head.last = null;
    }

    private V maintain(K key, V val){ //维护函数
        ValueNode<K,V> node= cache.get(key);
        if(node == null){
            return null; //如果不包含则不需维护
        }
        if(val != null){
            node.value = val; //更新数据
        }
        if(removeNodeIfNotTail(node)){ //移动到队尾
            pushBack(node);
        }
        return node.value;
    }

    public V get(K key){
        return maintain(key, null);
    }

    public void put(K key, V value){
        if(maintain(key, value) == null){ //原来没有此数据就新增
            ValueNode<K, V> newNode = new ValueNode<>(key, value);
            pushBack(newNode);
            cache.put(key, newNode);
        }
        while(cache.size() > cacheSize){
            cache.remove(head.key);
            removeHead();
        }
    }

    public V delete(K key){
        ValueNode<K, V> node= cache.remove(key);
        if(node == null){return null;}
        if(!removeNodeIfNotTail(node)){
            if(cache.isEmpty()){
                head = tail = null;
            }
            else{
                node.last.next = null;
                tail = node.last;
            }
        }
        return node.value;
    }

    public static void main(String[] args) {
//        LRUCache<Integer, Integer> lru = new LRUCache<>(2);
//        lru.put(1,1);
//        lru.put(2,2);
//        System.out.println(lru.get(1));
//        lru.put(3,3);
//        System.out.println(lru.get(2));
//        lru.put(4,4);
//        System.out.println(lru.get(1));
//        System.out.println(lru.get(3));
//        System.out.println(lru.get(4));
        LRUCache<Integer, Integer> lru = new LRUCache<>(2);
        lru.put(2,1);
        System.out.println(lru.delete(2));
        System.out.println(lru.get(2));
        lru.put(3,2);
        System.out.println(lru.get(2));
        System.out.println(lru.get(3));
    }
}

